package com.algorithm.learning.base.动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/9/2 22:36
 **/
public class 打印一个字符串的全部排列 {

    /**
     * str[0..i-1] 已经做好决定了
     * str[i...] 都有机会来到i位置
     * i终止位置，str当前的值，就是一种结果
     * @param str
     * @param index
     * @param ans
     */
    public static void process(char[] str, int index, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(str));
            return;
        }
        // 此时index还没到终止位置, 从index往后所有的位置，都可以与index位置进行交换
        for (int i = index; i < str.length; i++) { // 尝试index后面所有的字符都可以交换
            // 交换
            swap(str, index, i);
            process(str, index + 1, ans);
            // 这里要注意还原现场，因为这里的char[] str是公用的
            swap(str, index, i);
        }
    }

    private static void swap(char[] str, int i, int j) {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }

    public static void processNotRepeat(char[] str, int index, List<String> ans) {
        if (index == str.length) {
            ans.add(String.valueOf(str));
            return;
        }
        // 26个字母
        boolean[] visit = new boolean[26];
        for (int i = index; i < str.length; i++) {
            if (!visit[str[i] - 'a']) {
                visit[str[i] - 'a'] = true;
                swap(str, index, i);
                process(str, index + 1, ans);
                // 这里要注意还原现场，因为这里的char[] str是公用的
                swap(str, index, i);
            }
        }
    }

    public static List<String> permutation(String str) {
        char[] chars = str.toCharArray();
        List<String> ans = new ArrayList<>();
        process(chars, 0, ans);
        return ans;
    }

    public static List<String> permutation2(String str) {
        char[] chars = str.toCharArray();
        List<String> ans = new ArrayList<>();
        processNotRepeat(chars, 0, ans);
        return ans;
    }


    public static void main(String[] args) {
        String str = "aabc";
        List<String> ans = permutation2(str);
        System.out.println(ans.size());
        for (String s : ans) {
            System.out.println(s);
        }
    }

}
